package labuladong.第一章;

import java.util.HashMap;
import java.util.Map;

/**
 * LRU
 */
public class LRUCache {
    // 双向链表结点
    class Node<K, V> {
        int key;
        int value;
        Node<Integer, Integer> prev;
        Node<Integer, Integer> next;
        public Node () {
            this.prev = this.next = null;
        }
        public Node (int key, int value) {
            this.key = key;
            this.value = value;
            this.prev = this.next = null;
        }
    }

    // 双向链表
    class DoubleList {
        Node<Integer, Integer> head;
        Node<Integer, Integer> tail;
        public DoubleList() {
            head = new Node<Integer, Integer>();
            tail = new Node<Integer, Integer>();
            head.next = tail;
            tail.prev = head;
        }
        // 添加结点
        public void addHead(Node<Integer, Integer> node) {

        }
        // 移除结点
        public void removeNode(Node<Integer, Integer> node) {

        }
        // 获取头结点
        public Node<Integer, Integer> getHead() {
            return head.next;
        }
        // 获取尾节点
        public Node<Integer, Integer> getTail() {
            return tail.prev;
        }
    }

    private int capacity;
    Map<Integer, Node<Integer, Integer>> map;
    static DoubleList doubleList;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>(capacity);
        doubleList = new DoubleList();
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node<Integer, Integer> node = map.get(key);
        doubleList.removeNode(node);
        doubleList.addHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node<Integer, Integer> node = map.get(key);
            node.value = value;
            doubleList.removeNode(node);
            doubleList.addHead(node);
            map.put(key, node);
        } else {
            if (map.size() == capacity) {
                Node<Integer, Integer> lastNode = doubleList.getTail();
                doubleList.removeNode(lastNode);
                map.remove(lastNode.key);
            }
            Node<Integer, Integer> newNode = new Node<Integer, Integer>(key, value);
            doubleList.addHead(newNode);
            map.put(key, newNode);
        }
    }
}
